using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		//ListNode* cur1 = list1,*cur2 = list2;
		if (list1 == nullptr)return list2;
		else if (list2 == nullptr)return list1;

		ListNode* ret = list1->val <= list2->val ? list1 : list2;
		ret == list1 ? list1 = list1->next : list2 = list2->next;
		ret->next = mergeTwoLists(list1, list2);
		return ret;
	}
};
